﻿class Solution
{
public:
	string longestPalindrome(string s)
	{
		// 1. 创建 dp 表 
		// 2. 初始化 
		// 3. 填表 
		// 4. 返回值 
		int n = s.size();
		vector<vector<bool>> dp(n, vector<bool>(n));
		int len = 1, begin = 0; // 标记最⻓⼦串的起始位置和⻓度 
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = i; j < n; j++)
			{
				if (s[i] == s[j])
					dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
				if (dp[i][j] && j - i + 1 > len) // 找出⼦串中最⻓的回⽂⼦串 
					len = j - i + 1, begin = i;
			}
		}
		return s.substr(begin, len);
	}
};